package com.gitee.feizns.explore.data_structure.linked_list.singly.removeZeroSumSublists;

/**
 * 从链表中删去总和值为零的连续节点
 *
 * 给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
 *
 * 删除完毕后，请你返回最终结果链表的头节点。
 *
 *  
 *
 * 你可以返回任何满足题目要求的答案。
 *
 * （注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
 * @author feizns
 * @since 2019/11/12
 */
public class RemoveZeroSum {

    public static void main(String[] args) {
        final ListNode node = removeZeroSum(create());
    }

    private static ListNode create() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(2);
        ret.next.next = new ListNode(3);
        ret.next.next.next = new ListNode(-3);
        ret.next.next.next.next = new ListNode(-2);
        return ret;
    }

    public static ListNode removeZeroSum(ListNode head) {
        ListNode[] arr = convertToArr(head, 0);
        later:
        for (int i = 0; i < arr.length; i++) {
            if ( arr[i] != null ) {
                int sum = arr[i].val;
                if ( sum == 0 ) {
                    arr[i] = null;
                    continue;
                }
                for (int j = i + 1; j < arr.length; j++) {
                    if ( arr[j] != null ) {
                        sum += arr[j].val;
                        if ( sum == 0 ) {
                            for (int k = i; k <= j; k++)
                                arr[k] = null;
                            i = -1;
                            continue later;
                        }
                    }
                }
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy;
        for (ListNode node : arr) {
            if ( node != null ) {
                tmp.next = node;
                tmp = tmp.next;
            }
        }
        tmp.next = null;
        return dummy.next;
    }

    static ListNode[] arr;

    private static ListNode[] convertToArr(ListNode node, int index) {
        if ( node != null ) {
            convertToArr(node.next, index + 1);
            arr[index] = node;
        } else
            arr = new ListNode[index];
        return arr;
    }

}
